package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * 1261. 在受污染的二叉树中查找元素
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/3 11:08
 */
public class FindElements {

    // ["FindElements","find","find"]
    //[[[-1,null,-1]],[1],[2]]
    //输出
    //[null,false,false]
    //预期结果
    //[null,false,true]

    public static void main(String[] args) {

        FindElements test = new FindElements(TreeNode.getInstance5());

        for (int i = 0; i < 20; i++) {
            System.out.println(i + "   " + test.find(i));
        }


    }

    long[] arr = new long[15626];
    long[] cache = new long[64];
    public FindElements(TreeNode root) {
        for (int i = 0; i < 64; i++) {
            cache[i] = 1L << i;
        }
        root.val = 0;
        arr[0] = 1L;
        find(root);
    }
    private void find(TreeNode node) {
        if (node.left != null) {
            int i = (node.val << 1) + 1;
            if ((i >> 6) < 15626) {
                arr[i >> 6] |= cache[i & 63];
                node.left.val = i;
                find(node.left);
            }
        }
        if (node.right != null) {
            int i = (node.val << 1) + 2;
            if ((i >> 6) < 15626) {
                arr[i >> 6] |= cache[i & 63];
                node.right.val = i;
                find(node.right);
            }
        }
    }
    public boolean find(int target) {
        return (arr[target >> 6] & cache[target & 63]) == cache[target & 63];
    }

}
